int fun(vector<int>& nums,int mid){
    int ans = 0;
    for(auto e : nums)
        ans += (e - 1)/mid + 1;
    return ans;
}
class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int left = 1,right = 5000000;
        while(left <= right){
            int mid = (left + right) >> 1;
            int a = fun(nums,mid);
            // cout << a <<' ' << left << ' ' << right << endl;
            if(a > threshold){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
};
long long fun(vector<int>& nums,long long mid,int totalTrips){
    long long ans = 0;
    for(auto e : nums){
        ans += mid/(long long)e;
        if(ans > totalTrips)
         return  ans;
    }
    return ans;
}
class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long left = 0,right = 1000000000000000;
        while(left <= right){
            long long mid = (left + right) >> 1;
            long long a = fun(time,mid, totalTrips);
            if(a >= totalTrips){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
            // cout << a << ' ' << left <<' ' << right << endl;
        }
        return left;
    }
};
bool fun(vector<int>& dist,int mid,double hour){
    double ans = 0;
    for(int i = 0;i < dist.size();i++){
        ans += (double)dist[i] / mid; 
        if(ans > hour){
            return false;
        }
        if(ans != int(ans))
            ans = (int) ans + 1;
    }
    return true;
}
class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int left = 0,right = 1e7 + 2;
        if(hour < dist.size() - 1) return -1;
        while(left <= right){
            int mid = (left + right) >> 1;
            bool a = fun(dist,mid,hour);
            if(a == false){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
            // cout << a <<' ' << left << ' ' << right << endl;
        }
        if(left == 1e7 + 3) return -1;
        return left;
    }
};
bool fun(vector<int>& weights,int mid, int days){
    int n = weights.size(), a = mid,time = 1;
    for(int left = 0;left < n;)
    {
        if(weights[left] <= a){
            a -= weights[left++];
        }else{
            a = mid;
            time++;
        }
        if(time > days){
            return false;
        }
    }
    // cout << time <<' ';
    return true;
}
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int left = 0,right = INT_MAX;
        while(left <= right){
            int mid = (left + right) >> 1;
            bool  a = fun(weights,mid,days);
            // cout << a << ' ' << left <<' ' << right << endl;
            if(a == false){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
};
bool fun(vector<int>& piles, int h,int v){
    int time = 0,n = piles.size(),a = 0;
    for(int i = 0;i <n;i++){
        // if(a < piles[i]){
        //     a += v;
        //     time++;
        // }else{
        //     a = 0,i++;
        // }
        time += (piles[i] - 1)/v + 1;
        if(time > h){
            return false;
        }
    }
    return true;
}
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1,right = INT_MAX/2;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(fun(piles,h,mid)){
                // 吃的完 吃慢点
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
};
using ll = long long;
vector<ll> vvv;
int fun2(ll a) {
    if(vvv.size() == 0){
        long long b = 0;
        while (b * (b + 1) <= 500005000000000) {
            vvv.push_back(b * (b + 1));
            // cout << b * (b + 1) <<' ';
            // 0 2 6 12 20 30 42 56 72 90 110 132 156 182 
            b++;
        }  
    }
    return max((ll)(ranges::upper_bound(vvv,a) - vvv.begin() - 1),(ll)0);
}
bool fun(vector<int>& workerTimes, int mountainHeight, ll time) {
    int hetight = 0, n = workerTimes.size();
    // 挖 x 米 需要（x）*(x + 1) / 2  * w[i] 秒
    // 
    // 1    1m-1s 2m-3s
    // 2    1m-2s 2m-6s
    // 6 = (2) * (2 + 1) / 2 * 2
    for (int i = 0; i < n; i++) {
        ll m = time * 2 / workerTimes[i];
        ll c = fun2(m);
        // cout << i << ' ' << c << ' ' << m << endl;
        mountainHeight -= c;
        if (mountainHeight <= 0) {
            return true;
        }
    }
    return false;
}
class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        ll left = 0, right = 50000500000000000;
        while (left <= right) {
            ll mid = (left + right) >> 1;
            // cout << left << ' ' << right << endl;
            if (fun(workerTimes, mountainHeight, mid)) {
                // 挖的完
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
class Solution {
public:
    int earliestSecondToMarkIndices(vector<int>& nums,
                                    vector<int>& changeIndices) {
        int n = nums.size(), m = changeIndices.size();
        if (m < n)
            return -1;
        vector<int> last_t(n);
        auto check = [&](int mx) -> bool {
            ranges::fill(last_t, -1); // 填充
            for (int t = 0; t < mx; t++) {
                last_t[changeIndices[t] - 1] = t; // 取最后一次出现
            }
            if (ranges::find(last_t, -1) != last_t.end()) {
                return false;           // 有一科不能进行考试
            }
            int cnt = 0;
            for(int i = 0;i < mx;i++){
                int idx = changeIndices[i] - 1; // 减一是下标转换
                if(i == last_t[idx]){
                    if(nums[idx] > cnt){
                        return false;
                    }
                    cnt -= nums[idx];
                }else{
                    cnt++;
                }
            }
            return true;
        };
        int left = n - 1, right = m + 1;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            (check(mid) ? right : left) = mid;
        }
        return right > m ? -1 : right;
    }
};